Friday, July 20, 2007 The New York Times original article link
Friday, July 20, 2007
The New York Times original article link
By
KENNETH CHANG
Published: July 20, 2007
Checkers has been solved.
A computer program named Chinook vanquished its human competitors at tournaments more than a decade ago. But now, in an article published Thursday on the Web site of the journal Science, the scientists at the University of Alberta who developed the program report that they have rigorously proved that Chinook, in a slightly improved version, cannot ever lose. Any opponent, human or computer, no matter how skilled, can at best achieve a draw.
In essence, that reduces checkers to the level of tic-tac-toe, for which the ideal game-playing strategy has been codified into an immutable strategy. But checkers — or draughts, as it is known in Britain — is the most complex game that has been solved to date, with some 500 billion billion possible board positions, compared with the 765 possibilities in tic-tac-toe.
Even with the advances in computers over the past two decades, it is still impossible, in practical terms, to compute moves for all 500 billion billion board positions. So, the researchers took the usual starting position and looked only at the positions that occurred during play.
“It’s a computational proof,” said Jonathan Schaeffer, a professor of computer science at the University of Alberta who led the effort. “It’s certainly not a formal mathematical proof.” That means it is impossible for anyone to check every calculation the computer has performed.
Because of the vast calculations, the researchers had to keep painstaking track of the data. Miscopying a single bit — a glitch that did occur every few months — could render their result incorrect if not caught and corrected. When an error was caught, calculations had to be restarted from that point. A checkers hobbyist has independently verified major components of the proof with another computer program.
Dr. Schaeffer began his quest in 1989, aiming to write software that could compete with top checkers players in the world. In April, 18 years later, he and his colleagues finished their computations.
“From my point of view, thank God it’s over,” Dr. Schaeffer said.
For an exercise in futility, anyone can play a game against the perfect Chinook at http://www.cs.ualberta.ca/~chinook/play/. (It is limited to 24 games at a time.)
The earlier incarnation of Chinook, relying on artificial intelligence techniques and the combined computing power of many computers, placed second in the 1990 United States championship behind Marion Tinsley, the world champion, who had won every tournament he had played in since 1950.
That achievement should have earned Chinook the right to challenge Dr. Tinsley, a professor of mathematics at Florida A&M University, for the world championship, but the American Checkers Federation and the English Draughts Association refused to sanction a match. After much wrangling in the checkers world, Dr. Tinsley and Chinook battled for the man-versus-machine checkers title in 1992.
Dr. Tinsley won, 4 to 2 with 33 draws. Chinook’s two wins were only the sixth and seventh losses for Dr. Tinsley since 1950. In a rematch two years later, Dr. Tinsley withdrew after six draws, citing health reasons. Cancer was diagnosed, and Dr. Tinsley died seven months later.
Chinook easily triumphed over other human challengers, but the unfinished match against Dr. Tinsley left lingering doubt whether Chinook could claim to be the best of all time.
The new research proves that Chinook is invincible in traditional checkers. In most tournament play, however, a match now starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving some hope for humans.
Alexander Moiseyev, the current world champion in what is known as three-move checkers, has never faced Chinook. He said he used computers to study and analyze games but did not play against them, and he readily conceded that people were no longer worthy competitors for computers.
“This time is over today,” he said. “It doesn’t bother me.” The next game Dr. Schaeffer hopes to conquer is poker, which is harder to solve, because players do not have complete knowledge of their opponents’ positions. Next week, his program, Polaris, will take on two professional poker players in Texas Hold ’Em for the $50,000 man-versus-machine world championship.
Soon, computers may not just be winning games, but taking people’s money, too.